Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs

摘要

In this paper, we explore the relationship between one of the most elementaryand important properties of graphs, the presence and relative frequency oftriangles, and a combinatorial notion of Ricci curvature. We employ adefinition of generalized Ricci curvature proposed by Ollivier in a generalframework of Markov processes and metric spaces and applied in graph theory byLin-Yau. In analogy with curvature notions in Riemannian geometry, we interpretthis Ricci curvature as a control on the amount of overlap betweenneighborhoods of two neighboring vertices. It is therefore naturally related tothe presence of triangles containing those vertices, or more precisely, thelocal clustering coefficient, that is, the relative proportion of connectedneighbors among all the neighbors of a vertex. This suggests to derive lowerRicci curvature bounds on graphs in terms of such local clusteringcoefficients. We also study curvature dimension inequalities on graphs,building upon previous work of several authors.